package com.lxl.quick;

import java.util.Arrays;

/**
 * @Classname HollandFlag
 * @Description 荷兰国旗
 * @Date 2021/8/19 14:47
 * @Created by LXLDEMO
 */
public class HollandFlag {
    public static void main(String[] args) {
        // 测试数据
        int arr[] = {-1,-2,-3,2,1,1,1,4,8,1,6,5};
        partition(arr,arr.length,1);
    }

    /**
     *
     * @param arr
     * @param len
     * @param pivot
     * @return
     */
    public static int partition(int[] arr,int len,int pivot){
        System.out.println("分界值 [" + pivot + "]");
        System.out.println("初始数据 " + Arrays.toString(arr)+"\n");

        int less = -1; // 记录比pivot小的值的下标 -1 表示没有
        int more = len; // 记录比pivot大的值的下标 arr.length表示没有

        System.out.println("分界值 [" + pivot + "]");
        int i=0;
        while (i<len&&less<more){
            if (arr[i]<pivot){
                swap(arr,i++,++less);
                System.out.println("小于"+Arrays.toString(arr));
            }else if (arr[i]>pivot&&i<more){// 因为是从左向右遍历 所以交换过来的数据（arr[i],原arr[--more]）并没有被判断 所以这里i不加一  且 要保证more和i的大小关系
                swap(arr,i,--more);
                System.out.println("大于"+Arrays.toString(arr));
            }else {
                i++;
            }
        }
        System.out.println("最终结果 " + Arrays.toString(arr)+"\n");






        // 以下代码用于打印结果
        System.out.println("小于"+pivot);
        System.out.print("[ ");
        for (int n =0;n<=less;n++){
            System.out.print(arr[n] + " ");
        }
        System.out.print("]");

        System.out.println("\n等于"+pivot);
        System.out.print("[ ");
        for (int n =less+1;n<more;n++){
            System.out.print(arr[n] + " ");
        }
        System.out.print("]");

        System.out.println("\n大于"+pivot);
        System.out.print("[ ");
        for (int n =more;n<len;n++){
            System.out.print(arr[n] + " ");
        }
        System.out.print("]");
        return i;
    }



    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}
